//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {
    public static void main(String[] args) {
        //1.BM14链表的奇偶重排（双指针）
        public ListNode oddEvenList (ListNode head) {
            if(head == null) {
                return null;
            }
            ListNode odd = head;
            ListNode even = head.next;
            ListNode evenHead = even;
            while(even != null && even.next != null) {
                odd.next = even.next;
                odd = odd.next;
                even.next = odd.next;
                even = even.next;
            }
            odd.next = evenHead;
            return head;
        }
        //2.BM11链表相加||（基于反转链表）
        public ListNode addInList (ListNode head1, ListNode head2) {
            //反转head1
            ListNode h1 = reverse(head1);
            //反转head2
            ListNode h2 = reverse(head2);
            ListNode newhead = new ListNode(-1);
            ListNode head = newhead;
            ListNode cur1 = h1;
            ListNode cur2 = h2;
            int ret = 0;
            while (cur1 != null || cur2 != null) {
                int tmp = ret;
                if (cur1 != null) {
                    tmp += cur1.val;
                    cur1 = cur1.next;
                }
                if (cur2 != null) {
                    tmp += cur2.val;
                    cur2 = cur2.next;
                }
                ret = tmp / 10;
                ListNode newNode = new ListNode(tmp % 10);
                head.next = newNode;
                head = newNode;
            }
            if(ret > 0) {
                ListNode newNode = new ListNode(ret);
                head.next = newNode;
                head = newNode;
            }
            return reverse(newhead.next);
        }
        private ListNode reverse(ListNode head) {
            ListNode cur = head;
            ListNode prve = null;
            ListNode tmp = null;
            while (cur != null) {
                tmp = cur.next;
                cur.next = prve;
                prve = cur;
                cur = tmp;
            }
            return prve;
        }
    }
}